#-*- coding: utf-8 -*-
from ListeChainee import *
from copy import copy

def merge(a, b):
    """
    Les listes données doivent être triées dans l'ordre croissant.
    La liste résultante n'aura pas de références vers les paramètres.
    Les data doivent être des types immuables.
    >>> a = ListeChainee(1, 2, 3)
    >>> b = ListeChainee(4, 5, 6)
    >>> print merge(a, b)
    [1, 2, 3, 4, 5, 6]
    >>> a = ListeChainee(2, 4, 6, 8, 10)
    >>> b = ListeChainee(1, 3, 5, 7)
    >>> print merge(a, b)
    [1, 2, 3, 4, 5, 6, 7, 8, 10]
    >>> a = ListeChainee(2, 4, 6, 8, 10)
    >>> b = ListeChainee(1, 3, 5, 7)
    >>> print merge(b, a)
    [1, 2, 3, 4, 5, 6, 7, 8, 10]
    >>> a = ListeChainee()
    >>> b = ListeChainee(1, 2, 3)
    >>> print merge(a, b)
    [1, 2, 3]
    >>> a = ListeChainee()
    >>> b = ListeChainee(1, 2, 3)
    >>> print merge(b, a)
    [1, 2, 3]
    """
    tmp = ListeChainee() #nouvelle
    cont = True #indicateur pour continuer
    ap = a.head #pointeur vers a
    bp = b.head #pointeur vers b
    while cont:
        if ap==None or bp==None:
            cont = False #on arrête (impossible de comparer !)
        else:
            if ap.data<bp.data:
                tmp.insertEnd(ap.data)
                ap = ap.next #on avance
            else:
                tmp.insertEnd(bp.data)
                bp = bp.next #on avance
    #on ajoute ce qui reste 
    tmp.insertEnd(ListeChainee(ap) + ListeChainee(bp))
    return tmp


if __name__=='__main__':
    import doctest
    doctest.testmod()
